<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3271：回忆之殿</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">回忆之殿</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">回忆之殿</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                回忆之殿                </h1>
                <p>时间限制：2s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div style="text-indent: 21pt"><span style="font-size: medium">22世纪，3013年，在专制的统治和残酷的生存竞争下，回忆早已被人们所抛弃。本该有感情、有灵魂的人们已经彻底沦为统治者的血肉机器，如傀儡一般日夜工作着，如傀儡一般走向战场，如傀儡一般出生，也如傀儡一般死亡。</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">&ldquo;&hellip;&hellip;抛弃了回忆的人，是没有未来的。&rdquo;</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">魔法结社，一群觉醒了意识的人们为了反抗霸权统治而组成的团体，致力于唤醒人们的灵魂。经过超过10年的努力，终于掌握了能够改变世界的终极魔法&mdash;&mdash;回忆之殿。</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">秋，魔法结社的首席魔法师，将要启动回忆之殿。</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">回忆之殿由一个回路构成，回路上等距离地环状分布着m个结界。每个结界的中心是一个巨大的魔法柱，结界的周围由不超过n个魔法晶石等距离排列环绕而成。每个原始结界上的魔法晶石都和中间的魔法柱之间有魔法通路，同时也和相邻的魔法晶石之间有魔法通路（特别的，如果结界的周围只有1个魔法晶石，那么该魔法晶石有1条绕过魔法柱一圈并连向自己的魔法通路，如果结界的周围只有2个魔法晶石，那么这两个魔法晶石之间有2条魔法通路分别绕过魔法柱的两侧）。那么显然，由x个魔法晶石组成的原始结界有2x条魔法通路。当然，一个原始结界也可以仅由魔法柱组成，此时魔法柱没有任何连出的魔法通路。</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium"><img height="129" alt="" width="511" src="../file/3271_0.jpg" /></span></div>
<div style="text-indent: 21pt">
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"><span style="font-size: medium"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">对于成型的结界，中心的魔法柱和周围的每个魔法晶石之间都有且只有</span><span lang="EN-US"><font face="Times New Roman">1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">条通路，也就是说，由</span><span lang="EN-US"><font face="Times New Roman">x</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个魔法晶石组成的成型的结界是由原始结界中删除</span><span lang="EN-US"><font face="Times New Roman">x</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">条魔法通路，使结界成为一个&ldquo;树形&rdquo;连通结构形成，我们称这个连通结构为&ldquo;魔法阵&rdquo;。由于魔法晶石是环绕魔法柱分布的，所以两个魔法阵是不同的魔法阵，当且仅当其中一个魔法阵不能通过旋转的方式与另一个魔法阵相同。</span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"><span style="font-size: medium"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><img height="124" alt="" width="547" src="../file/3271_1.jpg" /></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"></p>
<span style="font-size: medium"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">回忆之殿的魔法一共需要启动</span><span lang="EN-US"><font face="Times New Roman">t</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">次，第</span><span lang="EN-US"><font face="Times New Roman">i</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">次启动需要布置一个由</span><span lang="EN-US"><font face="Times New Roman">m</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个魔法阵总共</span><span lang="EN-US"><font face="Times New Roman">i-1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个魔法晶石构成的回路。同样的，由于回路是环状分布的，所以两个回忆之殿不同当且仅当其中一个回忆之殿的魔法阵不能通过旋转的方式与另一个回忆之殿对应魔法阵全部相同。</span></p>
</span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"><span style="font-size: medium"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><img height="132" alt="" width="558" src="../file/3271_2.jpg" /></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"></p>
<span style="font-size: medium"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">现在，在秋酱施展魔法之前，他想要知道，对于每一次启动回忆之殿，总共有几种可能的本质不同的魔法晶石布置方案满足条件，由于方案可能很多，只要输出答案模</span><span lang="EN-US"><font face="Times New Roman">12289</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">的结果就可以了。</span></p>
</span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"><span style="font-size: medium"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">&ldquo;嗯</span><span lang="EN-US"><font face="Times New Roman">~</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">果然，还是不能忘记啊。&rdquo;</span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 21pt; mso-char-indent-count: 2.0; mso-pagination: widow-orphan"></p>
</span></span></div></p><hr/><h3>输入格式</h3><p><p class="MsoNormalIndent" style="margin: 0cm 0cm 0pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">包括</span><span lang="EN-US"><font face="Times New Roman">1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行</span><span lang="EN-US"><font face="Times New Roman">3</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个正整数</span><span lang="EN-US"><font face="Times New Roman">m,n,t</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，意义如题所述。</span></span></p>
<p></p></p><hr/><h3>输出格式</h3><p><p class="MsoNormalIndent" style="margin: 0cm 0cm 0pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">输出文件</span><span lang="EN-US"><font face="Times New Roman">rikoru.out</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">包括</span><span lang="EN-US"><font face="Times New Roman">t+1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行，对于第</span><span lang="EN-US"><font face="Times New Roman">i</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行应该包含</span><span lang="EN-US"><font face="Times New Roman">1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个非负整数表示由</span><span lang="EN-US"><font face="Times New Roman">i-1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个魔法结晶启动的回忆之殿可能的形态数。</span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; mso-pagination: widow-orphan"></p></p><hr/><h3>样例输入</h3><pre>3 2 4

</pre><hr/><h3>样例输出</h3><pre>1
1
4
7
12
</pre><hr/><h3>提示</h3><p><p><span style="font-size: medium">Case 0&amp;Case 1: m,n&lt;=4;</span></p>
<p><span style="font-size: medium">Case 2&amp;Case 3: m&lt;=4000,n=1;</span></p>
<p><span style="font-size: medium">Case 4&amp;Case 5: m=1,n&lt;=4000;</span></p>
<p><span style="font-size: medium">Case 6&amp;Case 7:m,n&lt;=4000,n&lt;=4000,t&lt;=10;</span></p>
<p><span style="font-size: medium">Case 8&amp;Case 9:m,n&lt;=4000,n&lt;=4000,t&lt;=4000;</span></p>
<p><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; For All Case t&lt;=m*n.</span></p>
<p></p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3271" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3271" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>